Skymark Airlines được thành lập vào tháng 11 năm 1996 với tư cách là một hãng hàng không nội địa độc lập sau khi bãi bỏ quy định của ngành hàng không Nhật Bản và bắt đầu hoạt động vào ngày 19 tháng 9 năm 1998. Nó ban đầu được sở hữu bởi một tập đoàn các nhà đầu tư do công ty du lịch NGA đứng đầu và đứng đầu là chủ tịch của H H Saw Sawada;[8] một nhà đầu tư lớn đầu tiên khác là công ty cho thuê Orix. Kế hoạch kinh doanh ban đầu của nó kêu gọi nó có trụ sở tại Sân bay Itami ở Osaka.[9] Takashi Ide, cựu giám đốc điều hành của British Airways tại Nhật Bản, được thuê làm CEO của công ty vào năm 1998.[10]

Skymark đã có thể có được sáu vị trí tại Sân bay Haneda ở Tokyo vào tháng 3 năm 1997 và chuyển trụ sở chính đến quận Hamamatsucho của Tokyo vào tháng 3 năm 1998. Chuyến bay theo lịch trình đầu tiên của hãng từ Haneda đến Fukuoka là vào ngày 19 tháng 9 năm 1998; họ đã thêm các tuyến từ Itami đến Fukuoka và Sapporo vào năm 1999, nhưng đã đình chỉ các tuyến này vào năm 2000 để cung cấp nhiều chuyến bay hơn trên tuyến Haneda-Fukuoka.[11]

Năm 2002, Skymark đã nhận một máy bay Boeing 767 thứ ba và bắt đầu dịch vụ trên tuyến Haneda-Kagoshima, cũng như dịch vụ thuê tàu từ Haneda đến Seoul. Năm 2003, với chiếc 767 thứ tư được thuê khô từ All Nippon Airways, hãng đã bắt đầu dịch vụ cho Aomori và Tokushima.[11]